/**
 * 
 */
package leetCode;

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * @author zhong
 *
 */
public class MinimizeMalwareSpread {
	public int minMalwareSpread(int[][] graph, int[] initial) {
		boolean[] affected = new boolean[graph.length];
		for (int i : initial) {
			affected[i] = true;
		}
		boolean[] newAffected = new boolean[graph.length];
		System.arraycopy(affected, 0, newAffected, 0, graph.length);
		List<List<Integer>> afectedSubGraph = getAfectedSubGraph(graph, newAffected);
		int maxCnt = 0;
		int res = 0;
		for (List<Integer> subG : afectedSubGraph) {
			Collections.sort(subG);
			for (Integer node : subG) {
				int deep = DFSMaxDeep(node, graph, affected, new HashSet<Integer>());
				if (deep > maxCnt) {
					maxCnt = deep;
					res = node;
				}
			}
		}
		return res;
	}

	private int DFSMaxDeep(Integer node, int[][] graph, boolean[] affected, HashSet<Integer> visited) {
		// 对每个邻接点
		visited.add(node);
		int sum = 1;
		for (int i = 0; i < affected.length; i++) {
			if (graph[node][i] == 1 && !affected[i] && !visited.contains(i)) {
				int whiteCnt = DFSMaxDeep(i, graph, affected, visited);
				if (whiteCnt == 0) {
					return 0;
				}
				sum += whiteCnt;
			}
		}
		return sum;
	}

	/**
	 * 求连续最多的白的
	 * 
	 * @param node
	 * @param graph
	 * @param affected
	 * @return
	 */
	private int BFSMaxDeep(Integer node, int[][] graph, boolean[] affected) {
		Queue<Integer> queue = new LinkedList<>();
		queue.add(node);
		boolean[] visited = new boolean[graph.length];
		while (!queue.isEmpty()) {
			Integer cur = queue.poll();

		}
		return 0;
	}

	private List<List<Integer>> getAfectedSubGraph(int[][] graph, boolean[] affected) {
		List<List<Integer>> res = new ArrayList<>();
		boolean added[] = new boolean[affected.length];
		for (int i = 0; i < graph.length; i++) {
			if (!added[i] && affected[i]) {
				List<Integer> subGraph = BFS(i, graph, affected, added);
				res.add(subGraph);
			}
		}
		return res;
	}

	private List<Integer> BFS(int i, int[][] graph, boolean[] affected, boolean[] added) {
		List<Integer> res = new ArrayList<>();
		res.add(i);
		added[i] = true;
		Queue<Integer> queue = new LinkedList<>();
		queue.offer(i);
		while (!queue.isEmpty()) {
			int k = queue.poll();
			for (int j = 0; j < graph.length; j++) {
				if (!added[j] && graph[k][j] == 1) {
					affected[j] = true;
					queue.add(j);
					added[j] = true;
					res.add(j);
				}
			}
		}
		return res;
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		int[][] graph = { { 1, 1, 0, 0 }, { 1, 1, 1, 0 }, { 0, 1, 1, 1 }, { 0, 0, 1, 1 } };// { { 1, 1, 0 }, { 1, 1, 1
																							// }, { 0, 1, 1 } };// { {
																							// 1, 1, 1 }, { 1, 1, 1 }, {
																							// 1, 1, 1 } };
		int[] initial = { 0, 1 };
		System.out.println(new MinimizeMalwareSpread().minMalwareSpread(graph, initial));
	}

}
